Part 12: UC Berkeley EECS

Part 12 - UC Berkeley EECS


=== Trash World Inbox ===

silentsnack has some improvements for last week's puzzle.
Reduces it to 14 from my 15. The trickiest part is getting the right way to rearrange the code, I guess.

Yep. The gaps in the code should basically handle each case manually, by LINKing to whatever side the REPL didn't handle yet. This way all unnecessary jumps are gone. By the way, using numeric MARK names doesn't make the code any easier to read.


=== UC Berkeley - Department of Electrical Engineering & Computer Sciences ===

Would you say you had friends?



Two votes for Sure I do.

Sure I do.

Yeah? Like Ghast? The EXAPUNKS?
But you never say anything to them.
Do friends not communicate back and forth?
Either way, this is good data for me.

I'm pretty sure it's TCP that communicates back and forth, lady.



I know real-life phreakers war-dialing business numbers sometimes found fresh dial tones... that would allow you to dial international numbers, billing the business for the costs.



Looks like Ember wants something from UC Berkeley. That's at least closer to home than whatever that Russian thing was.

There's another file I want to grab.
They tried to wipe everything clean, but luckily, there's a set of backups.
Always keep a backup, right?



Everyone who voted seems to agree.

Right.

You never know what's going to happen.
Data is more fragile than people think.

Make regular backups, folks.


OST: Leave No Trace

So, I got a bit curious and did some digging. The UC Berkeley department of EECS exists, and that logo is very similar to the style used on their official website - since around 2005ish. The web archive pages from before that look quite different. Bit of an anachronism, but I doubt Zachtronics expected anyone to dig this deep.

Our assignment:
- Locate the specified host (either tape-1, tape-2, or tape-3) and then locate the specified entry (ПАСЬЯНС) in the tape backup file in that host (file 200). Create a file in your host containing the entry's data.
- The names of the target host and entry are available in file 300.
- For more information see "Accessing Data in Legacy Storage Systems" in the first issue in the zine.

We also have a maximum size of 75 this time, quite a change from the 50 we've seen before.

All those files named 200 have a similar structure - a whole bunch of numbers and then some words and numbers.



Are those student grades?

Anyway, to the zine!



There's another page about hard drive arrays but that doesn't seem very relevant here.

Now, before I start you should notice there's no LINK ids back from most of those hosts. We can only travel counterclockwise. That's gonna be a bit limiting.

I could either start with two EXAs: one who stays home and communicates the info from 300 and one who goes find the data; or with one who does everything. I decided to go with the single EXA solution because it seems simpler - with two EXAs, how would you tell the home one it should switch from sending the TAPE number to sending the entry name?



Since it's a bit annoying to go back and forth in a file I decided to copy the TAPE number into X. It might save a cycle or two over the alternative.
It's not possible to TEST against the host name directly, I need to use the special HOST command to copy it into a register and TEST against that. Luckily I have T available for that.

Once the EXA tracks down the tape file, it copies the entry name to X, WIPEs the home file and GRABs the tape. Now to search for the entry.

Those zeroes just before the tape's index are probably padding, because all tapes are the same length. If that's true we can just SEEK straight to the start of the index and start searching from there. A SEEK 126 seems to do the trick.

After a bit of tinkering I settled on this:
SEEK 2 is necessary for every cycle (to go to the next entry's name), and it's best to have it at the start to prevent some awkwardness when the EXA finds the right entry. Having the initial SEEK only go to 124 allows me to do this without too much overhead.



It makes sense to put the first value in T - I'm gonna need T for test results, and the first value contains the start position which I only need once anyway. The other value goes into X and the EXA can SEEK to the start position.

Now we run into a little problem - the EXA is going to have to copy a whole lot of data but it can only hold one file at once. I really don't see any other solution than introducing a second EXA and sending all the data over M.

I added this to XA:
It automatically stops when it's done.

And I made XB that simply does this:
Getting close to a solution. The only problem is that XB never halts.

I could send XA home to KILL XB when it's done, but in situations like this I prefer using a special "end of transmission" packet. It might be slower, but we'll see.



Here's my first working solution. When XA is done it sends -9999 over M. If that's a valid entry in a tape file this won't work. I'll have to try and see.

XB now needs to use X as an intermediate register so it can TEST for -9999. Since I don't want to store -9999 in the file, the EXA should immediately exit the loop in that case. I can do that by, unintuitively, putting the COPY to F at the start of the next loop. To store the first entry correctly, there's an initial COPY from M before the loop. This assumes that we never get a zero-size entry but I think a zero-size entry wouldn't make sense anyway.



142/34/7.

Top percentile has 97/28/7. What can we do better?

First of all, the activity can't possibly be improved. We need 7 LINKs to get to tape 3, and sometimes we simply need to go there. Remember, to score a solution, it takes the worst-case scenario out of all the test runs.

Looking at cycles, there's a simple thing I missed in my initial solution: I don't need the TEST command to end the loops if I just set up the T register correctly.
124/33/7. As it happens 0 isn't used as a valid number either so I can use that as the end-of-message packet. And I also used T for the for loop in XA now.

Next thing to look at is unrolling loops. There's no immediate obvious way to do this because every loop needs to check something which requires a TJMP/FJMP anyway. However, I can save many loops by making use of the fact there's a minimal data size - the file we're looking for is always at least 15 entries long. We really don't need to check if we're done before that.
96/61/7, cycle count already better than the top percentile somehow. But I still have some more ideas.

First, the earlier plan of using an EXA that stays home to send the data from the file so the 'main' EXA doesn't have to carry that file around.

I changed XA to LINK in the first cycle and read from M in the second cycle. It also reads from M when it would normally read the name of the data entry.
XB simply starts with GRAB 300; COPY F M; COPY F M; WIPE before it creates the new file. It had to wait anyway.

Result 95/63/7. I think the saved cycle comes from the fact that XA doesn't have to WIPE the file anymore. It isn't more because it now has to wait for XB's M.

We could perhaps fix that by having XA read from M later, but that would introduce other problems. No, I have a better idea: parallelism during the initial search:
This way, the new EXA is already LINKing to the next tape node while this one is still checking. I reuse the FINDENTRY mark here - the first command after it is a SEEK that requires the EXA to hold a file; so it quickly makes the EXA crash.

It's a good idea... but we have one problem. After the correct tape is found, the last REPL'd EXA just keeps going round and round, and if we allow it to keep going until the tape handling is done, it will pick up the tape file and cause trouble. We need to get rid of it.

Luckily we have plenty of spare lines of code and enough time while the other EXAs do their thing.





My final solution. XC basically waits in the host with file 243 for the number of cycles until XA makes a full circle. Just doing a couple KILLs then isn't quite enough, because XA tries to REPL and move on to another run around the block while the KILLs are happening and it's unpredictable whether the one that stays or the one that LINKs gets killed first. Instead I have XC itself REPL and sit there so that XA can't link, and it can be killed without a fuss.

This brings my best scores to 92 cycles, 33 size, and 7 activity. And that's where I'll stop. We know the size can definitely be improved, and perhaps the cycles can go even lower. Share your improvements.

Kind of a shame what happened here.
There was some interesting research going on.



Here's the vote for this update.

But first for something special...

.

.

.

.

.

.

Part 12.5 - ПАСЬЯНС

So that file that Ember made us get from UC Berkeley? Turns out it's a program I can run. Let's see what it is.




Ah, this old game.
It's just how I remember it...
A testbed for goal-seeking behaviors regulated by emotional reasoning.
Do you like to play games?



Eh, sometimes?

Picky, are we?
Well, this one's fun.


New OST: ПАСЬЯНС

A card game?



Ember made me go through all that for a game of Solitaire?

In fact, the Russian name directly translates to Solitaire. Like many other languages, they use the French name for the game, Patience.

Zachtronics always adds some sort of Solitaire bonus minigame to their games. In fact, their recent title NERTS! is entirely a Solitaire game, and an online competitive one at that. It's free on Steam.

There are three Steam achievements tied to this game: One for winning a round, one for winning 10 rounds and one for winning 100 rounds. Even though I wiped my save for this Let's Play, it still has my win count from the original save - I suppose it got that from Steam's achievement tracker.



The game isn't too hard, but it's good to stop and think before each move. It's easy to get yourself stuck. Also, make use of the free cell.



Getting some nice ordered stacks.



Stacks of four face cards on an empty spot are turned upside down and can't be moved again. Not that it matters - you can't move face cards anywhere except on other face cards of the same suit or an empty spot anyway.



I think I won?

If you ever need a break from hacking, this is a good choice.
It's mildly active, and not as taxing as putting together EXAs.
See how I am keeping your needs in mind.



And another vote.



Installing this game put a shortcut in my dock (to the right of Ember) so I can play it whenever I feel like it.